﻿ #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
	vector<int> kWeakestRows(vector<vector<int>>& mat, int k)
	{
		int m = mat.size(), n = mat[0].size();
		//pair: ﬁrst为战斗力， second为行索引
		vector<pair<int, int>> power;
		for (int i = 0; i < m; ++i)
		{
			int left = 0, right = n - 1, pos = -1;
			while (left <= right)
			{
				int mid = (left + right) / 2;
				if (mat[i][mid] == 0)
				{
					right = mid - 1;
				}
				else
				{
					pos = mid;
					left = mid + 1;
				}
			}
			power.push_back(pair<int, int>(pos + 1, i));
		}
		//创建小堆
		priority_queue q(greater<pair<int, int>>(), move(power));
		vector<int> ans;
		for (int i = 0; i < k; ++i)
		{
			ans.push_back(q.top().second);
			q.pop();
		}
		return ans;
	}
};